Data describing objects in three dimensions continues to be acquired. Uses for this data continue to increase. One use for three dimensional data is to determine relationships between objects. For example, it may be useful to know how far a first object is from a second object. Similarly, it may be useful to know whether a first object intersects a second object. It may also be useful to know whether a first object is inside another object. For example, it may be useful to know whether a probe is located inside a tumor or outside a tumor. Similarly, it may be useful to know whether a certain container is located on a dock or inside a ship.
Conventionally, this “point in polyhedron” problem has been addressed using random ray shooting. In random ray shooting, random points located outside the polyhedron are identified and a ray is shot from a query point, the point for which the inside/outside polyhedron determination is desired, to the random points. A “face crossing” algorithm may count the number of faces crossed by the ray to determine whether the query point is inside the polyhedron. If the ray intersects a vertex it is discarded and another random point may be selected. A finite number of random rays may be produced and analyzed, if they are even analyzed at all. Thus, face crossing algorithms may not be deterministic due to special cases that are not handled by conventional random ray shooting approaches.